package com.whitedust.top10;

import java.util.Random;

/**
 * @author A
 * @since 2025/11/2 13:01
 */

public class Top8 {
    private final Random rand = new Random();
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    private void quickSort(int[] nums, int left, int right) {
        //如果有序了就退出
        boolean ordered = true;
        for (int i = left; i < right; i++) {
            if (nums[i] > nums[i + 1]) {
                ordered = false;
                break;
            }
        }
        if (ordered) return;
        //没有有序的情况下继续分治
        int p = partition(nums, left, right);
        quickSort(nums, left, p - 1);
        quickSort(nums, p + 1, right);
    }

    private int partition(int[] nums, int left, int right) {
        int i = left+rand.nextInt(right-left+1);
        int pivot = nums[i];
        swap(nums,i,left);
        i=left+1;
        int j = right;
        while(i<=j){
            while(i<=j&&nums[i]<pivot)i++;
            while(i<=j&&nums[j]>pivot)j--;
            if(i<=j){
                swap(nums,i,j);
                i++;
                j--;
            }
        }
        swap(nums,left,j);
        return j;
    }
}
